package my.jwds.p432;

import com.alibaba.fastjson.JSONObject;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class AllOne {

    public static void main(String[] args) {

        AllOne obj = new AllOne();
        long start = System.currentTimeMillis();
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));

        String val = "[\"AllOne\",\"inc\",\"inc\",\"inc\",\"inc\",\"getMaxKey\",\"inc\",\"inc\",\"inc\",\"dec\",\"inc\",\"inc\",\"inc\",\"getMaxKey\"]\n" +
                "[[],[\"hello\"],[\"goodbye\"],[\"hello\"],[\"hello\"],[],[\"leet\"],[\"code\"],[\"leet\"],[\"hello\"],[\"leet\"],[\"code\"],[\"code\"],[]]";
        String invoke = val.split("\n")[0];
        String param = val.split("\n")[1];
        String iv[] = JSONObject.parseObject(invoke,String[].class);
        String pa[][] = JSONObject.parseObject(param,String[][].class);

        String[]res = new String[iv.length];
        for (int i = 0; i < iv.length; i++) {
            String s = iv[i];
            if (s.equals("inc")){
                obj.inc(pa[i][0]);
            }else if (s.equals("dec")){
                obj.dec(pa[i][0]);
            }else if (s.equals("getMaxKey")){
                res[i] = obj.getMaxKey();
            }else if (s.equals("getMinKey")){
                res[i] = obj.getMinKey();
            }
        }
        System.out.println(Arrays.toString(res));

    }
    class CountString{
        String str;
        int count;
        CountString next;
        CountString prev;
        public CountString(String str, int count) {
            this.str = str;
            this.count = count;
        }

        public CountString(String str, int count, CountString next, CountString prev) {
            this.str = str;
            this.count = count;
            this.next = next;
            this.prev = prev;
        }
    }
    Map<String,CountString> map = new HashMap<>();
    Map<Integer,CountString> chains = new HashMap<>();
    CountString begin;
    CountString end;
    public AllOne() {
        begin = new CountString(null,Integer.MAX_VALUE);
        end = new CountString(null,Integer.MIN_VALUE);
        begin.next = end;
        end.prev = begin;
    }

    public void inc(String key) {
        CountString countString;
        if (!map.containsKey(key)){
            countString = new CountString(key,1,end,end.prev);
            end.prev.next = countString;
            end.prev = countString;
            map.put(key,countString);
        }else{
            countString = map.get(key);
            CountString chain = this.chains.get(countString.count);
            if (countString != chain){
                countString.prev.next = countString.next;
                countString.next.prev = countString.prev;

                countString.prev = chain.prev;
                countString.next = chain;
                chain.prev = countString;
                countString.prev.next = countString;
            }else{
                chains.put(countString.count,countString.next);
            }
            countString.count++;
        }
        if (!chains.containsKey(countString.count)){
            chains.put(countString.count,countString);
        }
    }

    public void dec(String key) {
        CountString countString = map.get(key);
        CountString chain = chains.get(key);
        if (chain == countString)chains.put(countString.count,chain.next);
        countString.count--;
        if (countString.count == 0){
            map.remove(key);
            countString.next.prev = countString.prev;
            countString.prev.next = countString.next;
        }else {
            chain = chains.get(countString.count);
            countString.prev.next = countString.next;
            countString.next.prev = countString.prev;

            countString.prev = chain.prev;
            countString.next = chain;
            chain.prev = countString;
            countString.prev.next = countString;

            chains.put(countString.count,countString);
        }
    }

    public String getMaxKey() {
        if (begin.next == end)return "";
        return begin.next.str;
    }

    public String getMinKey() {
        if (begin.next == end)return "";
        return end.prev.str;
    }
}